package oj;

public class Num1714qSort {
    public int[] smallestK(int[] arr, int k) {
        int[] ret=new int[k];
        if(arr.length==0 || k==0){
            return ret;
        }
        quickSort(arr,0,arr.length-1,k);
        for (int i = 0; i < ret.length; i++) {
            ret[i]=arr[i];
        }
        return ret;
    }

    private void quickSort(int[] arr, int l, int r,int k) {
        if(l>=r){
            return;
        }
        int p=partition(arr,l,r);
        if(p==k-1){
            return;
        }else if(p<k-1){
            quickSort(arr,p+1,r,k);
        }else {
            quickSort(arr,l,p-1,k);
        }
    }

    private int partition(int[] arr, int l, int r) {
        int v=arr[l];
        int j=l;
        for (int i =l+1; i <=r; i++) {
            if(arr[i]<v){
                swap(arr,j+1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return j;

    }
    private void swap(int[] nums, int i, int j) {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}
